package gold.digger;

import gold.utils.InputUtil;
import javafx.util.Pair;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1162 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {

        List<Pair<Integer, Integer>> dir = new ArrayList<>(Arrays.asList(new Pair<Integer, Integer>(-1, 0),
                new Pair<Integer, Integer>(1, 0), new Pair<Integer, Integer>(0, -1), new Pair<Integer, Integer>(0, 1)));

        public int maxDistance(int[][] grid) {
            Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
            int n = grid.length, ans = -1, curDepth = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 1) queue.add(new Pair<>(i, j));
                }
            }

            while (!queue.isEmpty()) {
                int size = queue.size();
                ++curDepth;

                for (int i = 0; i < size; i++) {
                    Pair<Integer, Integer> cur = queue.poll();
                    grid[cur.getKey()][cur.getValue()] = 2;

                    for (Pair<Integer, Integer> dpt : dir) {
                        int nx = cur.getKey() + dpt.getKey(), ny = cur.getValue() + dpt.getValue();
                        if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                            if (grid[nx][ny] == 0) {
                                // 当前是海洋
                                grid[nx][ny] = 2; // 杜绝重复遍历海洋
                                ans = Math.max(ans, curDepth);
                                queue.add(new Pair<>(nx, ny));
                            }
                        }
                    }
                }
            }

            return ans;
        }
    }

    class Solution_Other {
        public int maxDistance(int[][] grid) {
            int n = grid.length;
            Deque<int[]> d = new ArrayDeque<>();
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 1) {
                        d.add(new int[]{i, j});
                        map.put(i * n + j, 0);
                    }
                }
            }
            int ans = -1;
            int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            while (!d.isEmpty()) {
                int[] poll = d.poll();
                int dx = poll[0], dy = poll[1];
                int step = map.get(dx * n + dy);
                for (int[] di : dirs) {
                    int nx = dx + di[0], ny = dy + di[1];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                    if (grid[nx][ny] != 0) continue;
                    grid[nx][ny] = step + 1;
                    d.add(new int[]{nx, ny});
                    map.put(nx * n + ny, step + 1);
                    ans = Math.max(ans, step + 1);
                }
            }
            return ans;
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.maxDistance(InputUtil.toDoubleIntegerArray("[[1,0,1],[0,0,0],[1,0,1]]")));
        System.out.println(solution.maxDistance(InputUtil.toDoubleIntegerArray("[[1,0,0],[0,0,0],[0,0,0]]")));
        System.out.println(solution.maxDistance(InputUtil.toDoubleIntegerArray("[[1,0,0,0,0,1,0,0,0,1],[1,1,0,1,1,1,0,1,1,0],[0,1,1,0,1,0,0,1,0,0],[1,0,1,0,1,0,0,0,0,0],[0,1,0,0,0,1,1,0,1,1],[0,0,1,0,0,1,0,1,0,1],[0,0,0,1,1,1,1,0,0,1],[0,1,0,0,1,0,0,1,0,0],[0,0,0,0,0,1,1,1,0,0],[1,1,0,1,1,1,1,1,0,0]]")));
    }

    public static void main(String[] args) throws Exception {
        LC1162 an = new LC1162();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
